package com.lry.basic.algorithm.floodfill;

public class NumOfWater {
    int[][] g;
    public int numOfWater(int[][] grid) {
        if(null==grid||grid.length==0) return 0;
        int num = 0;
        g = grid;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1){
                    dfs(i,j);
                    num++;//湖泊的个数+1
                }
            }
        }
        return num;
    }
    private void dfs(int i,int j){
        g[i][j] = 0;
        for(int dx=-1;dx<=1;dx++){
            for(int dy=-1;dy<=1;dy++){
                if(dx==0||dy==0){
                    int nx = i+dx;
                    int ny = j+dy;
                    if(nx>=0&&nx<g.length&&ny>=0&&ny<g[0].length&&g[nx][ny]==1){
                        dfs(nx,ny);
                    }
                }
            }
        }
    }


    public static void main(String[] args) {
        System.out.println(new NumOfWater().numOfWater(new int[][]{{1,1,0,1,1}, {1,0,0,0,0}, {0, 0,0,0,1}, {1,1,0,1,1}}));
    }

}
